package com.sheng.leetcode.year2023.month02.day27;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2023/02/27
 * <p>
 * 1144. 递减元素使数组呈锯齿状<p>
 * <p>
 * 给你一个整数数组 nums，每次 操作 会从中选择一个元素并 将该元素的值减少 1。<p>
 * 如果符合下列情况之一，则数组 A 就是 锯齿数组：<p>
 * 每个偶数索引对应的元素都大于相邻的元素，即 A[0] > A[1] < A[2] > A[3] < A[4] > ...<p>
 * 或者，每个奇数索引对应的元素都大于相邻的元素，即 A[0] < A[1] > A[2] < A[3] > A[4] < ...<p>
 * 返回将数组 nums 转换为锯齿数组所需的最小操作次数。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [1,2,3]<p>
 * 输出：2<p>
 * 解释：我们可以把 2 递减到 0，或把 3 递减到 1。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [9,6,1,6,2]<p>
 * 输出：4<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length <= 1000<p>
 * 1 <= nums[i] <= 1000<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/decrease-elements-to-make-array-zigzag">1144. 递减元素使数组呈锯齿状</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1144 {

    @Test
    public void test01() {
//        int[] nums = {1, 2, 3};
//        int[] nums = {9, 6, 1, 6, 2};
//        int[] nums = {2, 7, 10, 9, 8, 9};
        int[] nums = {7, 4, 8, 9, 7, 7, 5};
        System.out.println(new Solution().movesToMakeZigzag(nums));
    }
}

class Solution {
    public int movesToMakeZigzag(int[] nums) {
        // 分别计算两种情况下将数组 nums 变为锯齿数组所需要的操作次数
        int odd = 0, even = 0;
        int[] ints = Arrays.copyOf(nums, nums.length);
        for (int i = 0; i < nums.length; i += 2) {
            // 该位置是偶数
            if (i - 1 >= 0 && nums[i] <= nums[i - 1]) {
                odd += nums[i - 1] - nums[i] + 1;
                nums[i - 1] = nums[i] - 1;
            }
            if (i + 1 < nums.length && nums[i] <= nums[i + 1]) {
                odd += nums[i + 1] - nums[i] + 1;
                nums[i + 1] = nums[i] - 1;
            }
        }
        for (int i = 1; i < ints.length; i += 2) {
            // 该位子是奇数
            if (i - 1 >= 0 && ints[i] <= ints[i - 1]) {
                even += ints[i - 1] - ints[i] + 1;
                ints[i - 1] = ints[i] - 1;
            }
            if (i + 1 < ints.length && ints[i] <= ints[i + 1]) {
                even += ints[i + 1] - ints[i] + 1;
                ints[i + 1] = ints[i] - 1;
            }
        }
        return Math.min(odd, even);
    }
}
